package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         139,
		Discription: "是否能从字典中选单词（可重复）组成指定字符串",
		Level:       2,
		Labels: map[string]int{
			"哈希表":  1,
			"动态规划": 1,
		},
	})
}

func WordBreak(s string, wordDict []string) bool {
	n := len(s)
	//dp表示所有单词是否能构成s[:i]的字符串
	dp := make([]bool, n+1)
	dp[0] = true
	wordMap := make(map[string]bool, 0)
	for _, word := range wordDict {
		wordMap[word] = true
	}
	for j := 1; j <= n; j++ {
		for i := j - 1; i >= 0; i-- {
			if wordMap[s[i:j]] {
				dp[j] = dp[i]
				if dp[j] {
					break
				}
			}
		}
	}

	return dp[n]
}
